package MyDS.BinarySearchTree;

public class BinarySearchTree {
    /**
     * 二叉树第i个结点
     *      左孩子：2*i+1
     *      右孩子：2*i-1
     *      父节点：(i-1)/2
     */
    private class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
        private TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    private TreeNode root;
    public BinarySearchTree(){
        root = null;
    }

    /**
     * 向以root为根的BST中插入一个新的结点val
     * @param root
     * @param val
     * @return
     */
    private TreeNode insertIntoBST(TreeNode root, int val){
        if (root == null) {
            return new TreeNode(val);
        }
        if(val < root.val){
            root.left = insertIntoBST(root.left,val);
        }else if(val > root.val){
            root.right = insertIntoBST(root.right,val);
        }
        return root;
    }
    public void insertIntoBST(int val){
        root = insertIntoBST(root, val);
    }

    /**
     * 查找
     * @param val
     * @return 返回查找的结点
     */
    private boolean contains(TreeNode root, int val){
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            // 找到了
            return true;
        }else if (val < root.val) {
            // 递归去左树中查找
            return contains(root.left,val);
        }else {
            // 递归去右树中查找
            return contains(root.right,val);
        }
    }
    public boolean contains(int val){ return contains(root, val); }

    /**
     * 删除
     * @param key
     * @return
     */
    private TreeNode deleteNode(TreeNode root, int key){
        if(root == null){
            return null;
        }
        if(key > root.val){  //去右子树删除
            root.right = deleteNode(root.right,key);
        }else if(key < root.val){   //去左子树删除
            root.left = deleteNode(root.left,key);
        }else{  //找到待删除结点
            if(root.left == null)   return root.right;  //1.待删除结点无左子树
            if(root.right == null)  return root.left;   //2.待删除结点无右子树
            //3.待删除结点有左右子树
            root.val = minNode(root);   //用右子树中的最小值替换当前结点
            root.right = deleteNode(root.right, root.val);//删除右子树中最小结点

        }
        return root;
    }
    public TreeNode deleteNode(int key){ return deleteNode(root, key); }

    private int minNode(TreeNode root){
        root = root.right;
        while(root.left != null){
            root = root.left;
        }
        return root.val;
    }

    /**
     * 先序遍历以root为根的BST
     * @param root
     */
    private void preOrder(TreeNode root){
        if(root == null){
            return ;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void preOrder(){
        preOrder(root);
    }

}
